import java.util.HashMap;

public class PathSum1 {

    int ans = 0;
    HashMap<Long, Integer> map;
    public int pathSum(TreeNode root, int targetSum) {
        map = new HashMap<>();
        map.put(0l, 1);
        dfs(root, targetSum, 0);
        return ans;
    }

    public void dfs(TreeNode node, int target, long sum) {
        if (node == null) return;
        sum += node.val;
        ans += map.getOrDefault(sum - target, 0);
        map.put(sum, map.getOrDefault(sum, 0) + 1);
        dfs(node.left, target, sum);
        dfs(node.right, target, sum);
        map.put(sum, map.getOrDefault(sum, 0) - 1);
    }

    public void process(TreeNode node, int target, int sum) {
        if (node == null) {
            return;
        }
        sum += node.val;
        if (sum == target) ++ans;
        process(node.left, target, sum);
        process(node.right, target, sum);
        sum = 0;
        process(node.left, target, sum);
        process(node.right, target, sum);
    }

    public void process1(TreeNode node, int target, int sum) {
        if (node == null) return;
        sum += node.val;
        if (sum == target) ++ans;
        process1(node.left, target, sum);
        process1(node.right, target, sum);
    }

    public void process2(TreeNode node, int target) {
        if (node == null) return;
        process1(node, target, 0);
        process2(node.left, target);
        process2(node.right, target);
    }
}
